<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>排序算法之归并排序</title>
</head>
<body>
  <script type="text/javascript">
    // 归并排序
    function mergeSort(arr) {
      if (arr.length < 2) {
        return arr;
      }

      const middle = Math.floor(arr.length / 2);
      const leftArr = arr.slice(0, middle);
      const rightArr = arr.slice(middle);

      return merge(mergeSort(leftArr), mergeSort(rightArr));
    }

    // 合并左右数组
    function merge(leftArr, rightArr) {
      const arr = [];
      let l = 0, r = 0;

      while (l < leftArr.length && r < rightArr.length) {
        if (leftArr[l] < rightArr[r]) {
          arr.push(leftArr[l]);
          l++;
        } else {
          arr.push(rightArr[r]);
          r++;
        }
      }

      return arr.concat(leftArr.slice(l)).concat(rightArr.slice(r));
    }

    const arr = [10, 6, 3, 4, 8, 1, 2];
    console.log(mergeSort(arr));
  </script>
</body>
</html>